NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/std/c/706

Internet Message Format | 1996-08-06 | 3.4 KB

Path: inforamp.net!usenet
From: [e-mail] (Peter Curran)
Newsgroups: comp.std.c
Subject: Re: Restrictions on qsort compare function?
Date: Sat, 06 Apr 1996 17:23:42 GMT
Organization: PSC Enterprises
Message-ID: <4k69bf$[e-mail]>
References: <4iokop$[e-mail]> <4iqjar$[e-mail]> <4jgltp$[e-mail]> <[e-mail]> <4k28t4$[e-mail]> <[e-mail]>
Reply-To: [e-mail]
NNTP-Posting-Host: ts15-06.tor.istar.ca
X-Newsreader: Forte Free Agent 1.0.82

On Fri, 05 Apr 96 17:49:42 GMT in article <[e-mail]>
    Lawrence Kirby <[e-mail]> (Lawrence Kirby) wrote:

>If you can find any definition as to what the behaviour should be with your
>comparison function, explain what it is. Otherwise the behaviour is
>undefined.

IMHO, qsort() is required to return an array that is sorted according to the
criteria implied by the comparison function.  That is, at the point where qsort
returns, the array must match the order implied by the comparison function.  If
the comparison function definition is such that the order changes (although the
*definition* of the order must remain fixed), then IMHO the current wording of
the standard can be read as meaning that it is qsort's problem to deal with it.
This all hinges on how one interprets the word "considered" in the standard -
that is a very vague term to use in a standard, and IMHO can reasonably lead to
confusion.  If a "snapshot" is taken at the time qsort() returns, the array must
match order implied by the comparison function.  If the definition of the
comparison criteria cannot provide a definite sort order for the array at any
instant, then I agree that it is invalid, but if it does provide such an
definite order at any instant, then I think the current standard permits it.

Let me give another example of a problematic comparison function that seems to
me to satisfy all the requirements of the standard, but leads, I think, to
unintended problems for implementing qsort.

The comparison function returns 1 if the first value is greater than the second
value, or -1 if the second   However, if they are equal, the function then
compares the values of the pointers to the parameters (the actual arguments of
the function) - if the first is greater, 1 is returned, if the second is greater
-1 is returned, otherwise 0 is returned.

This function is a (misguided) attempt to create a stable sort.  It is only a
valid comparison function if qsort() only passes pointers to elements in the
array being sorted to the comparison function - otherwise, the pointer
comparisons are (probably) undefined.  This comparions function will "work"
(i.e. not produce undefined behaviour) for some possible implementations of
qsort(), but not others.  It would also produce a consistent sort order for some
implementations, but not others.  (I think Bubble Sort could be implemented with
these restriction.  Quicksort would be trickier, or a lot slower.)

So - is this comparison function legal or not?  I cannot see anything in the
standard that disallows it.  I think the requirement to avoid undefined
behaviour in this case can reasonably be interpreted as falling on qsort(), not
on the comparison function.  I am sure the committee never intended such a
think, but I the current standard can reasonably be read as containing them.

--
Peter Curran                               [e-mail]